package max.sort.insertion;

import max.Swap;

/**
 * O(n*n)
 *
 * @author Max
 * @date 2021年4月13日
 * @description
 */
public class InsertionSort {
	private static final InsertionSort insertionSort = new InsertionSort();

	private InsertionSort() {

	}

	public static InsertionSort instance() {
		return insertionSort;
	}

	public void sortAsc1(int[] array) {
		if (array == null || array.length < 2) {
			return;
		}
		for (int i = 1; i < array.length; i++) {
			int point = i;// 指向待交换数字
			for (int j = i - 1; j >= 0; j--) {// 实际上 point 是j+1,需要交换得j的上一位
				if (array[point] < array[j]) {
					Swap.array1(array, point, j);
					point = j;
				}
			}
		}
	}

	public void sortAsc2(int[] array) {
		if (array == null || array.length < 2) {
			return;
		}
		for (int i = 1; i < array.length; i++) {
			for (int j = i - 1; j >= 0 && array[j] > array[j + 1]; j--) {
				Swap.array1(array, j, j + 1);
			}
		}
	}
}
